Search

Kinetically constrained spin systems are toy models of supercooled liquids and amorphous solids. In this Perspective, we revisit the prototypical Fredrickson-Andersen (FA) kinetically constrained model from the viewpoint of K-core combinatorial optimization. Each kinetic cluster of the FA system, containing all the mutually visitable microscopic occupation configurations, is exactly the solution space of a specific instance of the K-core attack problem. The whole set of different jammed occupation patterns of the FA system is the configuration space of an equilibrium K-core problem. Based on recent theoretical results achieved on the K-core attack and equilibrium K-core problems, we discuss the thermodynamic spin glass phase transitions and the maximum occupation density of the fully unfrozen FA kinetic cluster, and the minimum occupation density and extreme vulnerability of the partially frozen (jammed) kinetic clusters. The equivalence between K-core attack and the fully unfrozen FA kinetic cluster also implies a new way of sampling K-core attack solutions., Comment: 14 pages, manuscript under review

We study the minimum dominating set problem as a representative combinatorial optimization challenge with a global topological constraint. The requirement that the backbone induced by the vertices of a dominating set should be a connected subgraph makes the problem rather nontrivial to investigate by statistical physics methods. Here we convert this global connectivity constraint into a set of local vertex constraints and build a spin glass model with only five coarse-grained vertex states. We derive a set of coarse-grained belief-propagation equations and obtain theoretical predictions on the relative sizes of minimum dominating sets for regular random and Erd\"os-R\'enyi random graph ensembles. We also implement an efficient message-passing algorithm to construct close-to-minimum connected dominating sets and backbone subgraphs for single random graph instances. Our theoretical strategy may also be inspiring for some other global topological constraints., Comment: 27pages,18 figures

We introduce a planted vertex cover problem on regular random graphs and study it by the cavity method. The equilibrium ordering phase transition of this binary-spin two-body interaction system is discontinuous in nature distinct from the continuous one of conventional Ising-like models, and it is dynamically blocked by an extensive free energy barrier. We discover that the disordered symmetric phase of this system may be locally stable with respect to the ordered phase at all inverse temperatures except for a unique eureka point $\beta_b$ at which it is only marginally stable. The eureka point $\beta_b$ serves as a backdoor to access the hidden ground state with vanishing free energy barrier. It exists in an infinite series of planted random graph ensembles and we determine their structural parameters analytically. The revealed new type of free energy landscape may also exist in other planted random-graph optimization problems at the interface of statistical physics and statistical inference., Comment: Preprint format, double-spaced, single column, 12 pages

The $K$-core of a graph is the unique maximum subgraph within which each vertex connects to $K$ or more other vertices. The optimal $K$-core attack problem asks to delete the minimum number of vertices from the $K$-core to induce its complete collapse. A hierarchical cycle-tree packing model is introduced here for this challenging combinatorial optimization problem. We convert the temporally long-range correlated $K$-core pruning dynamics into locally tree-like static patterns and analyze this model through the replica-symmetric cavity method of statistical physics. A set of coarse-grained belief propagation equations are derived to predict single vertex marginal probabilities efficiently. The associated hierarchical cycle-tree guided attack ({\tt hCTGA}) algorithm is able to construct nearly optimal attack solutions for regular random graphs and Erd\"os-R\'enyi random graphs. Our cycle-tree packing model may also be helpful for constructing optimal initial conditions for other irreversible dynamical processes on sparse random graphs., Comment: 25 pages, 8 figures

Lateral predictive coding is a recurrent neural network which creates energy-efficient internal representations by exploiting statistical regularity in sensory inputs. Here we investigate the trade-off between information robustness and energy in a linear model of lateral predictive coding analytically and by numerical minimization of a free energy. We observe several phase transitions in the synaptic weight matrix, especially a continuous transition which breaks reciprocity and permutation symmetry and builds cyclic dominance and a discontinuous transition with the associated sudden emergence of tight balance between excitatory and inhibitory interactions. The optimal network follows an ideal-gas law in an extended temperature range and saturates the efficiency upper-bound of energy utilization. These results bring theoretical insights on the emergence and evolution of complex internal models in predictive processing systems., Comment: 6 pages main text, supplementary text combined. This is an extensively revised version, containing new analytical results and numerical results

The criticality of the jamming transition responsible for amorphous solidification has been theoretically linked to the marginal stability of a thermodynamic Gardner phase. While the critical exponents of jamming appear independent of the preparation history, the pertinence of Gardner physics far from equilibrium is an open question. To fill this gap, we numerically study the nonequilibrium dynamics of hard disks compressed towards the jamming transition using a broad variety of protocols. We show that dynamic signatures of Gardner physics can be disentangled from the aging relaxation dynamics. We thus define a generic dynamic Gardner crossover regardless of the history. Our results show that the jamming transition is always accessed by exploring increasingly complex landscape, resulting in the anomalous microscopic relaxation dynamics that remains to be understood theoretically.

Predictive coding is a promising theoretical framework in neuroscience for understanding information transmission and perception. It posits that the brain perceives the external world through internal models and updates these models under the guidance of prediction errors. Previous studies on predictive coding emphasized top-down feedback interactions in hierarchical multi-layered networks but largely ignored lateral recurrent interactions. We perform analytical and numerical investigations in this work on the effects of single-layer lateral interactions. We consider a simple predictive response dynamics and run it on the MNIST dataset of hand-written digits. We find that learning will generally break the interaction symmetry between peer neurons, and that high input correlation between two neurons does not necessarily bring strong direct interactions between them. The optimized network responds to familiar input signals much faster than to novel or random inputs, and it significantly reduces the correlations between the output states of pairs of neurons., Comment: 12 pages, including 10 figures. To be published in the journal CTP

The K-core of a graph is the maximal subgraph within which each vertex is connected to at least K other vertices. It is a fundamental network concept for understanding threshold cascading processes with a discontinuous percolation transition. A minimum attack set contains the smallest number of vertices whose removal induces complete collapse of the K-core. Here we tackle this prototypical optimal initial-condition problem from the spin-glass perspective of cycle-tree maximum packing and propose a cycle-tree guided attack (CTGA) message-passing algorithm. The good performance and time efficiency of CTGA are verified on the regular random and Erd\"os-R\'enyi random graph ensembles. Our central idea of transforming a long-range correlated dynamical process to static structural patterns may also be instructive to other hard optimization and control problems., Comment: A label in Figure 3(b) was corrected

Network dismantling aims at breaking a network into disconnected components, and attacking vertices that intersect with many loops has proven to be a most efficient strategy. But the existing loop-focusing methods treat the short loops within densely connected local clusters (e.g., cliques) as equally important as the long loops connecting different clusters. Here we propose for highly clustered artificial and real-world networks a bipartite factor-graph formulation that retains all the long loops while simplifies the local dense clusters as individual factor nodes. We develop a mean-field theory for the associated long-loop feedback vertex set problem and apply its message-passing equation as a solver for network dismantling. The proposed factor-graph loop algorithm outperforms the current state-of-the-art graph loop algorithms by a considerable margin on various real networks. Further improvement in dismantling performance is achievable by optimizing the choice of the local dense clusters.

The planted p-spin interaction model is a paradigm of random-graph systems possessing both a ferromagnetic phase and a disordered phase with the latter splitting into many spin glass states at low temperatures. Conventional simulated annealing dynamics is easily blocked by these low-energy spin glass states. Here we demonstrate that, actually this planted system is exponentially dominated by a microcanonical polarized phase at intermediate energy densities. There is a discontinuous microcanonical spontaneous symmetry breaking transition from the paramagnetic phase to the microcanonical polarized phase. This transition can serve as a mechanism to avoid all the spin glass traps, and it is accelerated by the restart strategy of microcanonical random walk. We also propose an unsupervised learning problem on microcanonically sampled configurations for inferring the planted ground state., Comment: 11 pages; final version as accepted by PRE; minor corrections to reference and affiliation name

Random $K$-satisfiability ($K$-SAT) is a paradigmatic model system for studying phase transitions in constraint satisfaction problems and for developing empirical algorithms. The statistical properties of the random $K$-SAT solution space have been extensively investigated, but most earlier efforts focused on solutions that are typical. Here we consider maximally flexible solutions which satisfy all the constraints only using the minimum number of variables. Such atypical solutions have high internal entropy because they contain a maximum number of null variables which are completely free to choose their states. Each maximally flexible solution indicates a dense region of the solution space. We estimate the maximum fraction of null variables by the replica-symmetric cavity method, and implement message-passing algorithms to construct maximally flexible solutions for single $K$-SAT instances., Comment: During the PRE review process

The dynamical mechanism underlying the processes of anesthesia-induced loss of consciousness and recovery is key to gaining insights into the working of the nervous system. Previous experiments revealed an asymmetry between neural signals during the anesthesia and recovery processes. Here we obtain experimental evidence for the hysteresis loop and articulate the dynamical mechanism based on percolation on multilayer complex networks with self-similarity. Model analysis reveals that, during anesthesia, the network is able to maintain its neural pathways despite the loss of a substantial fraction of the edges. A predictive and potentially testable result is that, in the forward process of anesthesia, the average shortest path and the clustering coefficient of the neural network are markedly smaller than those associated with the recovery process. This suggests that the network strives to maintain certain neurological functions by adapting to a relatively more compact structure in response to anesthesia.

Social networks of engagement sometimes dramatically collapse. A widely adopted paradigm to understand this catastrophe dynamics is the threshold model but previous work only considered the irreversible K-core pruning process and the resulting kinetic activity patterns. Here we study the network alliance problem as a simplified model of social engagement by equilibrium statistical mechanics. Our theory reveals that the surviving kinetic alliances are out-of-equilibrium and atypical configurations which may become highly vulnerable to single-node-triggered cascading failures as they relax towards equilibrium. Our theory predicts that if the fraction of active nodes is beyond a certain critical value, the equilibrium (typical) alliance configurations could be protected from cascading failures by a simple least-effort local intervention strategy. We confirm these results by extensive Monte Carlo simulations., Comment: Revised with modified title, supplementary technical details included, to be published in Europhysics Letters (EPL)

We propose a method for solving statistical mechanics problems defined on sparse graphs. It extracts a small Feedback Vertex Set (FVS) from the sparse graph, converting the sparse system to a much smaller system with many-body and dense interactions with an effective energy on every configuration of the FVS, then learns a variational distribution parameterized using neural networks to approximate the original Boltzmann distribution. The method is able to estimate free energy, compute observables, and generate unbiased samples via direct sampling without auto-correlation. Extensive experiments show that our approach is more accurate than existing approaches for sparse spin glasses. On random graphs and real-world networks, our approach significantly outperforms the standard methods for sparse systems such as the belief-propagation algorithm; on structured sparse systems such as two-dimensional lattices our approach is significantly faster and more accurate than recently proposed variational autoregressive networks using convolution neural networks., Comment: 13 pages, 5 figures

Rock-Paper-Scissors (RPS), a game of cyclic dominance, is not merely a popular children's game but also a basic model system for studying decision-making in non-cooperative strategic interactions. Aimed at students of physics with no background in game theory, this paper introduces the concepts of Nash equilibrium and evolutionarily stable strategy, and reviews some recent theoretical and empirical efforts on the non-equilibrium properties of the iterated RPS, including collective cycling, conditional response patterns, and microscopic mechanisms that facilitate cooperation. We also introduce several dynamical processes to illustrate the applications of RPS as a simplified model of species competition in ecological systems and price cycling in economic markets., Comment: Mini-review article. 28 single-column pages

The binary perceptron is the simplest artificial neural network formed by $N$ input units and one output unit, with the neural states and the synaptic weights all restricted to $\pm 1$ values. The task in the teacher--student scenario is to infer the hidden weight vector by training on a set of labeled patterns. Previous efforts on the passive learning mode have shown that learning from independent random patterns is quite inefficient. Here we consider the active online learning mode in which the student designs every new Ising training pattern. We demonstrate that it is mathematically possible to achieve perfect (error-free) inference using only $N$ designed training patterns, but this is computationally unfeasible for large systems. We then investigate two Bayesian statistical designing protocols, which require $2.3 N$ and $1.9 N$ training patterns, respectively, to achieve error-free inference. If the training patterns are instead designed through deductive reasoning, perfect inference is achieved using $N\!+\!\log_{2}\!N$ samples. The performance gap between Bayesian and deductive designing strategies may be shortened in future work by taking into account the possibility of ergodicity breaking in the version space of the binary perceptron., Comment: 10 pages

Spontaneous symmetry breaking (SSB) in statistical physics is a macroscopic collective phenomenon. For the paradigmatic Q-state Potts model it means a transition from the disordered color-symmetric phase to an ordered phase in which one color dominates. Existing mean field theories imply that SSB in the microcanonical statistical ensemble (with energy being the control parameter) should be a continuous process. Here we study microcanonical SSB on the random-graph Potts model, and discover that the entropy is a kinked function of energy. This kink leads to a discontinuous phase transition at certain energy density value, characterized by a jump in the density of the dominant color and a jump in the microcanonical temperature. This discontinuous SSB in random graphs is confirmed by microcanonical Monte Carlo simulations, and it is also observed in bond-diluted finite-size lattice systems., Comment: 16 pages, extensively revised and improved

Previously, the controllability problem of a linear time-invariant dynamical system was mapped to the maximum matching (MM) problem on the bipartite representation of the underlying directed graph, and the sizes of MMs on random bipartite graphs were calculated analytically with the cavity method at zero temperature limit. Here we present an alternative theory to estimate MM sizes based on the core percolation theory and the perfect matching of cores. Our theory is much more simplified and easily interpreted, and can estimate MM sizes on random graphs with or without symmetry between out- and in-degree distributions. Our result helps to illuminate the fundamental connection between the controllability problem and the underlying structure of complex systems., Comment: 12 pages, 3 figures, and 1 table

The greedy leaf removal (GLR) procedure on a graph is an iterative removal of any vertex with degree one (leaf) along with its nearest neighbor (root). Its result has two faces: a residual subgraph as a core, and a set of removed roots. While the emergence of cores on uncorrelated random graphs was solved analytically, a theory for roots is ignored except in the case of Erd\"{o}s-R\'{e}nyi random graphs. Here we analytically study roots on random graphs. We further show that, with a simple geometrical interpretation and a concise mean-field theory of the GLR procedure, we reproduce the zero-temperature replica symmetric estimation of relative sizes of both minimal vertex covers and maximum matchings on random graphs with or without cores., Comment: 39 pages, 5 figures, and 3 tables

Direct Coupling Analysis (DCA) is a now widely used method to leverage statistical information from many similar biological systems to draw meaningful conclusions on each system separately. DCA has been applied with great success to sequences of homologous proteins, and also more recently to whole-genome population-wide sequencing data. We here argue that the use of DCA on the genome scale is contingent on fundamental issues of population genetics. DCA can be expected to yield meaningful results when a population is in the Quasi-Linkage Equilibrium (QLE) phase studied by Kimura and others, but not, for instance, in a phase of Clonal Competition. We discuss how the exponential (Potts model) distributions emerge in QLE, and compare couplings to correlations obtained in a study of about 3,000 genomes of the human pathogen Streptococcus pneumoniae., Comment: 9 pages, 5 figures

The emergence of quantum statistical mechanics from individual pure states of closed many-body systems is currently under intensive investigations. While most efforts have been put on the impacts of the direct interaction (i.e., the usual mutual interaction) between particles, here we study systematically and analytically the impacts of the exchange interaction, that arises from the particle indistinguishability. We show that this interaction leads an overwhelming number of Fock states to exhibit a structure, that can be resolved only by observables adjusted according to system's dynamical properties and from which thermal distributions emerge. This hidden thermal structure in Fock space is found to be related to the so-called limit shape of random geometric objects in mathematics. The structure enables us to uncover, for both ideal and nonideal Fermi gases, new mechanisms for the emergence of quantum statistical mechanics from individual eigenstates., Comment: 6 pages, 3 figures

Lower temperature leads to a higher probability of visiting low-energy states. This intuitive belief underlies most physics-inspired strategies for addressing hard optimization problems. For instance, the popular simulated annealing (SA) dynamics is expected to approach a ground state if the temperature is lowered appropriately. Here we demonstrate that this belief is not always justified. Specifically, we employ the cavity method to analyze the minimum strong defensive alliance problem and discover a bifurcation in the solution space, induced by an inflection point in the entropy--energy profile. While easily accessible configurations are associated with the lower-free-energy branch, the low-energy configurations are associated with the higher-free-energy branch within the same temperature range. There is a discontinuous phase transition between the high-energy configurations and the ground states, which generally cannot be followed by SA. We introduce an energy-clamping strategy to obtain superior solutions by following the higher-free-energy branch, overcoming the limitations of SA., Comment: 18 pages (including main text and appendices). The simulated annealing algorithm extensively revised, and discontinuous phase transition discussed

Learning Ising or Potts models from data has become an important topic in statistical physics and computational biology, with applications to predictions of structural contacts in proteins and other areas of biological data analysis. The corresponding inference problems are challenging since the normalization constant (partition function) of the Ising/Potts distributions cannot be computed efficiently on large instances. Different ways to address this issue have hence given size to a substantial methodological literature. In this paper we investigate how these methods could be used on much larger datasets than studied previously. We focus on a central aspect, that in practice these inference problems are almost always severely under-sampled, and the operational result is almost always a small set of leading (largest) predictions. We therefore explore an approach where the data is pre-filtered based on empirical correlations, which can be computed directly even for very large problems. Inference is only used on the much smaller instance in a subsequent step of the analysis. We show that in several relevant model classes such a combined approach gives results of almost the same quality as the computationally much more demanding inference on the whole dataset. We also show that results on whole-genome epistatic couplings that were obtained in a recent computation-intensive study can be retrieved by the new approach. The method of this paper hence opens up the possibility to learn parameters describing pair-wise dependencies in whole genomes in a computationally feasible and expedient manner., Comment: 15 pages, including 11 figures

Compressed sensing is an important problem in many fields of science and engineering. It reconstructs signals by finding sparse solutions to underdetermined linear equations. In this work we propose a deterministic and non-parametric algorithm SSD (Shortest-Solution guided Decimation) to construct support of the sparse solution under the guidance of the dense least-squares solution of the recursively decimated linear equation. The most significant feature of SSD is its insensitivity to correlations in the sampling matrix. Using extensive numerical experiments we show that SSD greatly outperforms L1-norm based methods, Orthogonal Least Squares, Orthogonal Matching Pursuit, and Approximate Message Passing when the sampling matrix contains strong correlations. This nice property of correlation tolerance makes SSD a versatile and robust tool for different types of real-world signal acquisition tasks., Comment: 10 pages, 9 figures and a MATLAB code. Updated reference; Efficient implementation of SSD using optimized dual ascent is achieved

The minimum feedback arc set problem asks to delete a minimum number of arcs (directed edges) from a digraph (directed graph) to make it free of any directed cycles. In this work we approach this fundamental cycle-constrained optimization problem by considering a generalized task of dividing the digraph into D layers of equal size. We solve the D-segmentation problem by the replica-symmetric mean field theory and belief-propagation heuristic algorithms. The minimum feedback arc density of a given random digraph ensemble is then obtained by extrapolating the theoretical results to the limit of large D. A divide-and-conquer algorithm (nested-BPR) is devised to solve the minimum feedback arc set problem with very good performance and high efficiency., Comment: 14 pages

Unsupervised learning in a generalized Hopfield associative-memory network is investigated in this work. First, we prove that the (generalized) Hopfield model is equivalent to a semi-restricted Boltzmann machine with a layer of visible neurons and another layer of hidden binary neurons, so it could serve as the building block for a multilayered deep-learning system. We then demonstrate that the Hopfield network can learn to form a faithful internal representation of the observed samples, with the learned memory patterns being prototypes of the input data. Furthermore, we propose a spectral method to extract a small set of concepts (idealized prototypes) as the most concise summary or abstraction of the empirical data., Comment: We found serious inconsistence between the numerical protocol described in the text and the actual numerical code used by the first author to produce the data. Because of this inconsistence, we decide to withdraw the preprint. The corresponding author (Hai-Jun Zhou) deeply apologizes for not being able to detect this inconsistence earlier

Directed networks such as gene regulation networks and neural networks are connected by arcs (directed links). The nodes in a directed network are often strongly interwound by a huge number of directed cycles, which lead to complex information-processing dynamics in the network and make it highly challenging to infer the intrinsic direction of information flow. In this theoretical paper, based on the principle of minimum-feedback, we explore the node hierarchy of directed networks and distinguish feedforward and feedback arcs. Nearly optimal node hierarchy solutions, which minimize the number of feedback arcs from lower-level nodes to higher-level nodes, are constructed by belief-propagation and simulated-annealing methods. For real-world networks, we quantify the extent of feedback scarcity by comparison with the ensemble of direction-randomized networks and identify the most important feedback arcs. Our methods are also useful for visualizing directed networks., Comment: 18 pages (main text and appendices, including 9 figures). This paper is related to and is an expansion of our previous post arXiv:1605.09257

Decycling and dismantling of complex networks are underlying many important applications in network science. Recently these two closely related problems were tackled by several heuristic algorithms, simple and considerably sub-optimal, on the one hand, and time-consuming message-passing ones that evaluate single-node marginal probabilities, on the other hand. In this paper we propose a simple and extremely fast algorithm, CoreHD, which recursively removes nodes of the highest degree from the $2$-core of the network. CoreHD performs much better than all existing simple algorithms. When applied on real-world networks, it achieves equally good solutions as those obtained by the state-of-art iterative message-passing algorithms at greatly reduced computational cost, suggesting that CoreHD should be the algorithm of choice for many practical purposes.

The collection of all the strongly connected components in a directed graph, among each cluster of which any node has a path to another node, is a typical example of the intertwining structure and dynamics in complex networks, as its relative size indicates network cohesion and it also composes of all the feedback cycles in the network. Here we consider finding an optimal strategy with minimal effort in removal arcs (for example, deactivation of directed interactions) to fragment all the strongly connected components into tree structure with no effect from feedback mechanism. We map the optimal network disruption problem to the minimal feedback arc set problem, a non-deterministically polynomial hard combinatorial optimization problem in graph theory. We solve the problem with statistical physical methods from spin glass theory, resulting in a simple numerical method to extract sub-optimal disruption arc sets with significantly better results than a local heuristic method and a simulated annealing method both in random and real networks. Our results has various implications in controlling and manipulation of real interacted systems., Comment: 22 pages, 11 figures

Covering problems are classical computational problems concerning whether a certain combinatorial structure 'covers' another. For example, the minimum vertex covering problem aims to find the smallest set of vertices in a graph so that each edge is incident to at least one vertex in that set. Interestingly, the computational complexity of the minimum vertex covering problem in graphs is closely related to the core percolation problem, where the core is a special subgraph obtained by the greedy leaf removal procedure. Here, by generalizing the greedy leaf removal procedure in graphs to hypergraphs, we introduce two generalizations of core percolation in graphs to hypergraphs, related to the minimum hyperedge cover problem and the minimum vertex cover problem on hypergraphs, respectively. We offer analytical solutions of these two core percolations for random hypergraphs with arbitrary vertex degree and hyperedge cardinality distributions. We also compute these two cores in several real-world hypergraphs, finding that they tend to be much smaller than their randomized counterparts. This result suggests that both the minimum hyperedge cover problem and the minimum vertex cover problem in those real-world hypergraphs can actually be solved in polynomial time. Finally, we map the minimum dominating set problem in graphs to the minimum hyperedge cover problem in hypergraphs. We show that our generalized greedy leaf removel procedure significantly outperforms the state-of-the-art method in solving the minimum dominating set problem.

A directed graph (digraph) is formed by vertices and arcs (directed edges) from one vertex to another. A feedback vertex set (FVS) is a set of vertices that contains at least one vertex of every directed cycle in this digraph. The directed feedback vertex set problem aims at constructing a FVS of minimum cardinality. This is a fundamental cycle-constrained hard combinatorial optimization problem with wide practical applications. In this paper we construct a spin glass model for the directed FVS problem by converting the global cycle constraints into local arc constraints, and study this model through the replica-symmetric (RS) mean field theory of statistical physics. We then implement a belief propagation-guided decimation (BPD) algorithm for single digraph instances. The BPD algorithm slightly outperforms the simulated annealing algorithm on large random graph instances. The predictions of the RS mean field theory are noticeably lower than the BPD results, possibly due to its neglect of cycle-caused long range correlations., Comment: 25 pages in total, including two appendices

A feedback vertex set (FVS) of an undirected graph contains vertices from every cycle of this graph. Constructing a FVS of sufficiently small cardinality is very difficult in the worst cases, but for random graphs this problem can be efficiently solved after converting it into an appropriate spin glass model [H.-J. Zhou, Eur. Phys. J. B 86 (2013) 455]. In the present work we study the local stability and the phase transition properties of this spin glass model on random graphs. For both regular random graphs and Erd\"os-R\'enyi graphs we determine the inverse temperature $\beta_l$ at which the replica-symmetric mean field theory loses its local stability, the inverse temperature $\beta_d$ of the dynamical (clustering) phase transition, and the inverse temperature $\beta_c$ of the static (condensation) phase transition. We find that $\beta_{l}$, $\beta_{d}$, and $\beta_c$ change with the (mean) vertex degree in a non-monotonic way; $\beta_d$ is distinct from $\beta_c$ for regular random graphs of vertex degrees $K\geq 64$, while $\beta_d$ are always identical to $\beta_c$ for Erd\"os-R\'enyi graphs (at least up to mean vertex degree $c=512$). We also compute the minimum FVS size of regular random graphs through the zero-temperature first-step replica-symmetry-breaking mean field theory and reach good agreement with the results obtained on single graph instances by the belief propagation-guided decimation algorithm. Taking together, this paper presents a systematic theoretical study on the energy landscape property of a spin glass system with global cycle constraints., Comment: 15 pages, including 7 figures and 3 appendices. Submitted to PRE in February 2016

We discuss the issue of distributed and cooperative decision-making in a network game of public service location. Each node of the network can choose to be a provider of service which is accessible to the provider itself and also to all the neighboring nodes. A node may also choose only to be a consumer, and then it has to pay a tax, and the collected tax is evenly distributed to all the service providers to remedy their cost. If nodes do not communicate with each other but make individual best-response decisions, the system will be trapped in an inefficient situation of high tax level. In this work we investigate a decentralized local-consensus selection mechanism, according to which nodes in need of service recommend their neighbors of highest local impact as candidate servers, and a node may become a server only if all its non-server neighbors give their assent. We demonstrate that this local-consensus mechanism, although only involving information exchange among neighboring nodes, leads to socially efficient solutions with tax level approaching the lowest possible value. Our results may help in understanding and improving collective problem-solving in various networked social systems and robotic systems., Comment: 9 pages, including 5 figures and 1 table

For a network formed by nodes and undirected links between pairs of nodes, the network optimal attack problem aims at deleting a minimum number of target nodes to break the network down into many small components. This problem is intrinsically related to the feedback vertex set problem that was successfully tackled by spin glass theory and an associated belief propagation-guided decimation (BPD) algorithm [H.-J. Zhou, Eur. Phys. J. B 86 (2013) 455]. In the present work we apply the BPD alrogithm (which has approximately linear time complexity) to the network optimal attack problem, and demonstrate that it has much better performance than a recently proposed Collective Information algorithm [F. Morone and H. A. Makse, Nature 524 (2015) 63--68] for different types of random networks and real-world network instances. The BPD-guided attack scheme often induces an abrupt collapse of the whole network, which may make it very difficult to defend., Comment: Final version (9 pages, including 5 figures and 1 table). Figure 3 is updated and contains more information than that of the accepted PRE paper

For a graph formed by vertices and weighted edges, a generalized minimum dominating set (MDS) is a vertex set of smallest cardinality such that the summed weight of edges from each outside vertex to vertices in this set is equal to or larger than certain threshold value. This generalized MDS problem reduces to the conventional MDS problem in the limiting case of all the edge weights being equal to the threshold value. We treat the generalized MDS problem in the present paper by a replica-symmetric spin glass theory and derive a set of belief-propagation equations. As a practical application we consider the problem of extracting a set of sentences that best summarize a given input text document. We carry out a preliminary test of the statistical physics-inspired method to this automatic text summarization problem., Comment: 11 pages, including 4 figures and 2 tables. To be published in Journal of Physics: Conference Series

We consider a one-step replica symmetry breaking description of the Edwards-Anderson spin glass model in 2D. The ingredients of this description are a Kikuchi approximation to the free energy and a second-level statistical model built on the extremal points of the Kikuchi approximation, which are also fixed points of a Generalized Belief Propagation (GBP) scheme. We show that a generalized free energy can be constructed where these extremal points are exponentially weighted by their Kikuchi free energy and a Parisi parameter $y$, and that the Kikuchi approximation of this generalized free energy leads to second-level, one-step replica symmetry breaking (1RSB), GBP equations. We then proceed analogously to Bethe approximation case for tree-like graphs, where it has been shown that 1RSB Belief Propagation equations admit a Survey Propagation solution. We discuss when and how the one-step-replica symmetry breaking GBP equations that we obtain also allow a simpler class of solutions which can be interpreted as a class of Generalized Survey Propagation equations for the single instance graph case., Comment: 34 pages, 4 figures